home *** CD-ROM | disk | FTP | other *** search
/ PC World Komputer 2010 April / PCWorld0410.iso / hity wydania / Ubuntu 9.10 PL / karmelkowy-koliberek-desktop-9.10-i386-PL.iso / casper / filesystem.squashfs / usr / src / linux-headers-2.6.31-14 / scripts / kallsyms.c < prev    next >
C/C++ Source or Header  |  2009-10-16  |  16KB  |  662 lines
  1. /* Generate assembler source containing symbol information
  2.  *
  3.  * Copyright 2002       by Kai Germaschewski
  4.  *
  5.  * This software may be used and distributed according to the terms
  6.  * of the GNU General Public License, incorporated herein by reference.
  7.  *
  8.  * Usage: nm -n vmlinux | scripts/kallsyms [--all-symbols] > symbols.S
  9.  *
  10.  *      Table compression uses all the unused char codes on the symbols and
  11.  *  maps these to the most used substrings (tokens). For instance, it might
  12.  *  map char code 0xF7 to represent "write_" and then in every symbol where
  13.  *  "write_" appears it can be replaced by 0xF7, saving 5 bytes.
  14.  *      The used codes themselves are also placed in the table so that the
  15.  *  decompresion can work without "special cases".
  16.  *      Applied to kernel symbols, this usually produces a compression ratio
  17.  *  of about 50%.
  18.  *
  19.  */
  20.  
  21. #include <stdio.h>
  22. #include <stdlib.h>
  23. #include <string.h>
  24. #include <ctype.h>
  25.  
  26. #ifndef ARRAY_SIZE
  27. #define ARRAY_SIZE(arr) (sizeof(arr) / sizeof(arr[0]))
  28. #endif
  29.  
  30. #define KSYM_NAME_LEN        128
  31.  
  32. struct sym_entry {
  33.     unsigned long long addr;
  34.     unsigned int len;
  35.     unsigned int start_pos;
  36.     unsigned char *sym;
  37. };
  38.  
  39. struct text_range {
  40.     const char *stext, *etext;
  41.     unsigned long long start, end;
  42. };
  43.  
  44. static unsigned long long _text;
  45. static struct text_range text_ranges[] = {
  46.     { "_stext",     "_etext"     },
  47.     { "_sinittext", "_einittext" },
  48.     { "_stext_l1",  "_etext_l1"  },    /* Blackfin on-chip L1 inst SRAM */
  49.     { "_stext_l2",  "_etext_l2"  },    /* Blackfin on-chip L2 SRAM */
  50. };
  51. #define text_range_text     (&text_ranges[0])
  52. #define text_range_inittext (&text_ranges[1])
  53.  
  54. static struct sym_entry *table;
  55. static unsigned int table_size, table_cnt;
  56. static int all_symbols = 0;
  57. static char symbol_prefix_char = '\0';
  58.  
  59. int token_profit[0x10000];
  60.  
  61. /* the table that holds the result of the compression */
  62. unsigned char best_table[256][2];
  63. unsigned char best_table_len[256];
  64.  
  65.  
  66. static void usage(void)
  67. {
  68.     fprintf(stderr, "Usage: kallsyms [--all-symbols] [--symbol-prefix=<prefix char>] < in.map > out.S\n");
  69.     exit(1);
  70. }
  71.  
  72. /*
  73.  * This ignores the intensely annoying "mapping symbols" found
  74.  * in ARM ELF files: $a, $t and $d.
  75.  */
  76. static inline int is_arm_mapping_symbol(const char *str)
  77. {
  78.     return str[0] == '$' && strchr("atd", str[1])
  79.            && (str[2] == '\0' || str[2] == '.');
  80. }
  81.  
  82. static int read_symbol_tr(const char *sym, unsigned long long addr)
  83. {
  84.     size_t i;
  85.     struct text_range *tr;
  86.  
  87.     for (i = 0; i < ARRAY_SIZE(text_ranges); ++i) {
  88.         tr = &text_ranges[i];
  89.  
  90.         if (strcmp(sym, tr->stext) == 0) {
  91.             tr->start = addr;
  92.             return 0;
  93.         } else if (strcmp(sym, tr->etext) == 0) {
  94.             tr->end = addr;
  95.             return 0;
  96.         }
  97.     }
  98.  
  99.     return 1;
  100. }
  101.  
  102. static int read_symbol(FILE *in, struct sym_entry *s)
  103. {
  104.     char str[500];
  105.     char *sym, stype;
  106.     int rc;
  107.  
  108.     rc = fscanf(in, "%llx %c %499s\n", &s->addr, &stype, str);
  109.     if (rc != 3) {
  110.         if (rc != EOF) {
  111.             /* skip line */
  112.             fgets(str, 500, in);
  113.         }
  114.         return -1;
  115.     }
  116.  
  117.     sym = str;
  118.     /* skip prefix char */
  119.     if (symbol_prefix_char && str[0] == symbol_prefix_char)
  120.         sym++;
  121.  
  122.     /* Ignore most absolute/undefined (?) symbols. */
  123.     if (strcmp(sym, "_text") == 0)
  124.         _text = s->addr;
  125.     else if (read_symbol_tr(sym, s->addr) == 0)
  126.         /* nothing to do */;
  127.     else if (toupper(stype) == 'A')
  128.     {
  129.         /* Keep these useful absolute symbols */
  130.         if (strcmp(sym, "__kernel_syscall_via_break") &&
  131.             strcmp(sym, "__kernel_syscall_via_epc") &&
  132.             strcmp(sym, "__kernel_sigtramp") &&
  133.             strcmp(sym, "__gp"))
  134.             return -1;
  135.  
  136.     }
  137.     else if (toupper(stype) == 'U' ||
  138.          is_arm_mapping_symbol(sym))
  139.         return -1;
  140.     /* exclude also MIPS ELF local symbols ($L123 instead of .L123) */
  141.     else if (str[0] == '$')
  142.         return -1;
  143.     /* exclude debugging symbols */
  144.     else if (stype == 'N')
  145.         return -1;
  146.  
  147.     /* include the type field in the symbol name, so that it gets
  148.      * compressed together */
  149.     s->len = strlen(str) + 1;
  150.     s->sym = malloc(s->len + 1);
  151.     if (!s->sym) {
  152.         fprintf(stderr, "kallsyms failure: "
  153.             "unable to allocate required amount of memory\n");
  154.         exit(EXIT_FAILURE);
  155.     }
  156.     strcpy((char *)s->sym + 1, str);
  157.     s->sym[0] = stype;
  158.  
  159.     return 0;
  160. }
  161.  
  162. static int symbol_valid_tr(struct sym_entry *s)
  163. {
  164.     size_t i;
  165.     struct text_range *tr;
  166.  
  167.     for (i = 0; i < ARRAY_SIZE(text_ranges); ++i) {
  168.         tr = &text_ranges[i];
  169.  
  170.         if (s->addr >= tr->start && s->addr <= tr->end)
  171.             return 1;
  172.     }
  173.  
  174.     return 0;
  175. }
  176.  
  177. static int symbol_valid(struct sym_entry *s)
  178. {
  179.     /* Symbols which vary between passes.  Passes 1 and 2 must have
  180.      * identical symbol lists.  The kallsyms_* symbols below are only added
  181.      * after pass 1, they would be included in pass 2 when --all-symbols is
  182.      * specified so exclude them to get a stable symbol list.
  183.      */
  184.     static char *special_symbols[] = {
  185.         "kallsyms_addresses",
  186.         "kallsyms_num_syms",
  187.         "kallsyms_names",
  188.         "kallsyms_markers",
  189.         "kallsyms_token_table",
  190.         "kallsyms_token_index",
  191.  
  192.     /* Exclude linker generated symbols which vary between passes */
  193.         "_SDA_BASE_",        /* ppc */
  194.         "_SDA2_BASE_",        /* ppc */
  195.         NULL };
  196.     int i;
  197.     int offset = 1;
  198.  
  199.     /* skip prefix char */
  200.     if (symbol_prefix_char && *(s->sym + 1) == symbol_prefix_char)
  201.         offset++;
  202.  
  203.     /* if --all-symbols is not specified, then symbols outside the text
  204.      * and inittext sections are discarded */
  205.     if (!all_symbols) {
  206.         if (symbol_valid_tr(s) == 0)
  207.             return 0;
  208.         /* Corner case.  Discard any symbols with the same value as
  209.          * _etext _einittext; they can move between pass 1 and 2 when
  210.          * the kallsyms data are added.  If these symbols move then
  211.          * they may get dropped in pass 2, which breaks the kallsyms
  212.          * rules.
  213.          */
  214.         if ((s->addr == text_range_text->end &&
  215.                 strcmp((char *)s->sym + offset, text_range_text->etext)) ||
  216.             (s->addr == text_range_inittext->end &&
  217.                 strcmp((char *)s->sym + offset, text_range_inittext->etext)))
  218.             return 0;
  219.     }
  220.  
  221.     /* Exclude symbols which vary between passes. */
  222.     if (strstr((char *)s->sym + offset, "_compiled."))
  223.         return 0;
  224.  
  225.     for (i = 0; special_symbols[i]; i++)
  226.         if( strcmp((char *)s->sym + offset, special_symbols[i]) == 0 )
  227.             return 0;
  228.  
  229.     return 1;
  230. }
  231.  
  232. static void read_map(FILE *in)
  233. {
  234.     while (!feof(in)) {
  235.         if (table_cnt >= table_size) {
  236.             table_size += 10000;
  237.             table = realloc(table, sizeof(*table) * table_size);
  238.             if (!table) {
  239.                 fprintf(stderr, "out of memory\n");
  240.                 exit (1);
  241.             }
  242.         }
  243.         if (read_symbol(in, &table[table_cnt]) == 0) {
  244.             table[table_cnt].start_pos = table_cnt;
  245.             table_cnt++;
  246.         }
  247.     }
  248. }
  249.  
  250. static void output_label(char *label)
  251. {
  252.     if (symbol_prefix_char)
  253.         printf(".globl %c%s\n", symbol_prefix_char, label);
  254.     else
  255.         printf(".globl %s\n", label);
  256.     printf("\tALGN\n");
  257.     if (symbol_prefix_char)
  258.         printf("%c%s:\n", symbol_prefix_char, label);
  259.     else
  260.         printf("%s:\n", label);
  261. }
  262.  
  263. /* uncompress a compressed symbol. When this function is called, the best table
  264.  * might still be compressed itself, so the function needs to be recursive */
  265. static int expand_symbol(unsigned char *data, int len, char *result)
  266. {
  267.     int c, rlen, total=0;
  268.  
  269.     while (len) {
  270.         c = *data;
  271.         /* if the table holds a single char that is the same as the one
  272.          * we are looking for, then end the search */
  273.         if (best_table[c][0]==c && best_table_len[c]==1) {
  274.             *result++ = c;
  275.             total++;
  276.         } else {
  277.             /* if not, recurse and expand */
  278.             rlen = expand_symbol(best_table[c], best_table_len[c], result);
  279.             total += rlen;
  280.             result += rlen;
  281.         }
  282.         data++;
  283.         len--;
  284.     }
  285.     *result=0;
  286.  
  287.     return total;
  288. }
  289.  
  290. static void write_src(void)
  291. {
  292.     unsigned int i, k, off;
  293.     unsigned int best_idx[256];
  294.     unsigned int *markers;
  295.     char buf[KSYM_NAME_LEN];
  296.  
  297.     printf("#include <asm/types.h>\n");
  298.     printf("#if BITS_PER_LONG == 64\n");
  299.     printf("#define PTR .quad\n");
  300.     printf("#define ALGN .align 8\n");
  301.     printf("#else\n");
  302.     printf("#define PTR .long\n");
  303.     printf("#define ALGN .align 4\n");
  304.     printf("#endif\n");
  305.  
  306.     printf("\t.section .rodata, \"a\"\n");
  307.  
  308.     /* Provide proper symbols relocatability by their '_text'
  309.      * relativeness.  The symbol names cannot be used to construct
  310.      * normal symbol references as the list of symbols contains
  311.      * symbols that are declared static and are private to their
  312.      * .o files.  This prevents .tmp_kallsyms.o or any other
  313.      * object from referencing them.
  314.      */
  315.     output_label("kallsyms_addresses");
  316.     for (i = 0; i < table_cnt; i++) {
  317.         if (toupper(table[i].sym[0]) != 'A') {
  318.             if (_text <= table[i].addr)
  319.                 printf("\tPTR\t_text + %#llx\n",
  320.                     table[i].addr - _text);
  321.             else
  322.                 printf("\tPTR\t_text - %#llx\n",
  323.                     _text - table[i].addr);
  324.         } else {
  325.             printf("\tPTR\t%#llx\n", table[i].addr);
  326.         }
  327.     }
  328.     printf("\n");
  329.  
  330.     output_label("kallsyms_num_syms");
  331.     printf("\tPTR\t%d\n", table_cnt);
  332.     printf("\n");
  333.  
  334.     /* table of offset markers, that give the offset in the compressed stream
  335.      * every 256 symbols */
  336.     markers = malloc(sizeof(unsigned int) * ((table_cnt + 255) / 256));
  337.     if (!markers) {
  338.         fprintf(stderr, "kallsyms failure: "
  339.             "unable to allocate required memory\n");
  340.         exit(EXIT_FAILURE);
  341.     }
  342.  
  343.     output_label("kallsyms_names");
  344.     off = 0;
  345.     for (i = 0; i < table_cnt; i++) {
  346.         if ((i & 0xFF) == 0)
  347.             markers[i >> 8] = off;
  348.  
  349.         printf("\t.byte 0x%02x", table[i].len);
  350.         for (k = 0; k < table[i].len; k++)
  351.             printf(", 0x%02x", table[i].sym[k]);
  352.         printf("\n");
  353.  
  354.         off += table[i].len + 1;
  355.     }
  356.     printf("\n");
  357.  
  358.     output_label("kallsyms_markers");
  359.     for (i = 0; i < ((table_cnt + 255) >> 8); i++)
  360.         printf("\tPTR\t%d\n", markers[i]);
  361.     printf("\n");
  362.  
  363.     free(markers);
  364.  
  365.     output_label("kallsyms_token_table");
  366.     off = 0;
  367.     for (i = 0; i < 256; i++) {
  368.         best_idx[i] = off;
  369.         expand_symbol(best_table[i], best_table_len[i], buf);
  370.         printf("\t.asciz\t\"%s\"\n", buf);
  371.         off += strlen(buf) + 1;
  372.     }
  373.     printf("\n");
  374.  
  375.     output_label("kallsyms_token_index");
  376.     for (i = 0; i < 256; i++)
  377.         printf("\t.short\t%d\n", best_idx[i]);
  378.     printf("\n");
  379. }
  380.  
  381.  
  382. /* table lookup compression functions */
  383.  
  384. /* count all the possible tokens in a symbol */
  385. static void learn_symbol(unsigned char *symbol, int len)
  386. {
  387.     int i;
  388.  
  389.     for (i = 0; i < len - 1; i++)
  390.         token_profit[ symbol[i] + (symbol[i + 1] << 8) ]++;
  391. }
  392.  
  393. /* decrease the count for all the possible tokens in a symbol */
  394. static void forget_symbol(unsigned char *symbol, int len)
  395. {
  396.     int i;
  397.  
  398.     for (i = 0; i < len - 1; i++)
  399.         token_profit[ symbol[i] + (symbol[i + 1] << 8) ]--;
  400. }
  401.  
  402. /* remove all the invalid symbols from the table and do the initial token count */
  403. static void build_initial_tok_table(void)
  404. {
  405.     unsigned int i, pos;
  406.  
  407.     pos = 0;
  408.     for (i = 0; i < table_cnt; i++) {
  409.         if ( symbol_valid(&table[i]) ) {
  410.             if (pos != i)
  411.                 table[pos] = table[i];
  412.             learn_symbol(table[pos].sym, table[pos].len);
  413.             pos++;
  414.         }
  415.     }
  416.     table_cnt = pos;
  417. }
  418.  
  419. static void *find_token(unsigned char *str, int len, unsigned char *token)
  420. {
  421.     int i;
  422.  
  423.     for (i = 0; i < len - 1; i++) {
  424.         if (str[i] == token[0] && str[i+1] == token[1])
  425.             return &str[i];
  426.     }
  427.     return NULL;
  428. }
  429.  
  430. /* replace a given token in all the valid symbols. Use the sampled symbols
  431.  * to update the counts */
  432. static void compress_symbols(unsigned char *str, int idx)
  433. {
  434.     unsigned int i, len, size;
  435.     unsigned char *p1, *p2;
  436.  
  437.     for (i = 0; i < table_cnt; i++) {
  438.  
  439.         len = table[i].len;
  440.         p1 = table[i].sym;
  441.  
  442.         /* find the token on the symbol */
  443.         p2 = find_token(p1, len, str);
  444.         if (!p2) continue;
  445.  
  446.         /* decrease the counts for this symbol's tokens */
  447.         forget_symbol(table[i].sym, len);
  448.  
  449.         size = len;
  450.  
  451.         do {
  452.             *p2 = idx;
  453.             p2++;
  454.             size -= (p2 - p1);
  455.             memmove(p2, p2 + 1, size);
  456.             p1 = p2;
  457.             len--;
  458.  
  459.             if (size < 2) break;
  460.  
  461.             /* find the token on the symbol */
  462.             p2 = find_token(p1, size, str);
  463.  
  464.         } while (p2);
  465.  
  466.         table[i].len = len;
  467.  
  468.         /* increase the counts for this symbol's new tokens */
  469.         learn_symbol(table[i].sym, len);
  470.     }
  471. }
  472.  
  473. /* search the token with the maximum profit */
  474. static int find_best_token(void)
  475. {
  476.     int i, best, bestprofit;
  477.  
  478.     bestprofit=-10000;
  479.     best = 0;
  480.  
  481.     for (i = 0; i < 0x10000; i++) {
  482.         if (token_profit[i] > bestprofit) {
  483.             best = i;
  484.             bestprofit = token_profit[i];
  485.         }
  486.     }
  487.     return best;
  488. }
  489.  
  490. /* this is the core of the algorithm: calculate the "best" table */
  491. static void optimize_result(void)
  492. {
  493.     int i, best;
  494.  
  495.     /* using the '\0' symbol last allows compress_symbols to use standard
  496.      * fast string functions */
  497.     for (i = 255; i >= 0; i--) {
  498.  
  499.         /* if this table slot is empty (it is not used by an actual
  500.          * original char code */
  501.         if (!best_table_len[i]) {
  502.  
  503.             /* find the token with the breates profit value */
  504.             best = find_best_token();
  505.  
  506.             /* place it in the "best" table */
  507.             best_table_len[i] = 2;
  508.             best_table[i][0] = best & 0xFF;
  509.             best_table[i][1] = (best >> 8) & 0xFF;
  510.  
  511.             /* replace this token in all the valid symbols */
  512.             compress_symbols(best_table[i], i);
  513.         }
  514.     }
  515. }
  516.  
  517. /* start by placing the symbols that are actually used on the table */
  518. static void insert_real_symbols_in_table(void)
  519. {
  520.     unsigned int i, j, c;
  521.  
  522.     memset(best_table, 0, sizeof(best_table));
  523.     memset(best_table_len, 0, sizeof(best_table_len));
  524.  
  525.     for (i = 0; i < table_cnt; i++) {
  526.         for (j = 0; j < table[i].len; j++) {
  527.             c = table[i].sym[j];
  528.             best_table[c][0]=c;
  529.             best_table_len[c]=1;
  530.         }
  531.     }
  532. }
  533.  
  534. static void optimize_token_table(void)
  535. {
  536.     build_initial_tok_table();
  537.  
  538.     insert_real_symbols_in_table();
  539.  
  540.     /* When valid symbol is not registered, exit to error */
  541.     if (!table_cnt) {
  542.         fprintf(stderr, "No valid symbol.\n");
  543.         exit(1);
  544.     }
  545.  
  546.     optimize_result();
  547. }
  548.  
  549. /* guess for "linker script provide" symbol */
  550. static int may_be_linker_script_provide_symbol(const struct sym_entry *se)
  551. {
  552.     const char *symbol = (char *)se->sym + 1;
  553.     int len = se->len - 1;
  554.  
  555.     if (len < 8)
  556.         return 0;
  557.  
  558.     if (symbol[0] != '_' || symbol[1] != '_')
  559.         return 0;
  560.  
  561.     /* __start_XXXXX */
  562.     if (!memcmp(symbol + 2, "start_", 6))
  563.         return 1;
  564.  
  565.     /* __stop_XXXXX */
  566.     if (!memcmp(symbol + 2, "stop_", 5))
  567.         return 1;
  568.  
  569.     /* __end_XXXXX */
  570.     if (!memcmp(symbol + 2, "end_", 4))
  571.         return 1;
  572.  
  573.     /* __XXXXX_start */
  574.     if (!memcmp(symbol + len - 6, "_start", 6))
  575.         return 1;
  576.  
  577.     /* __XXXXX_end */
  578.     if (!memcmp(symbol + len - 4, "_end", 4))
  579.         return 1;
  580.  
  581.     return 0;
  582. }
  583.  
  584. static int prefix_underscores_count(const char *str)
  585. {
  586.     const char *tail = str;
  587.  
  588.     while (*tail == '_')
  589.         tail++;
  590.  
  591.     return tail - str;
  592. }
  593.  
  594. static int compare_symbols(const void *a, const void *b)
  595. {
  596.     const struct sym_entry *sa;
  597.     const struct sym_entry *sb;
  598.     int wa, wb;
  599.  
  600.     sa = a;
  601.     sb = b;
  602.  
  603.     /* sort by address first */
  604.     if (sa->addr > sb->addr)
  605.         return 1;
  606.     if (sa->addr < sb->addr)
  607.         return -1;
  608.  
  609.     /* sort by "weakness" type */
  610.     wa = (sa->sym[0] == 'w') || (sa->sym[0] == 'W');
  611.     wb = (sb->sym[0] == 'w') || (sb->sym[0] == 'W');
  612.     if (wa != wb)
  613.         return wa - wb;
  614.  
  615.     /* sort by "linker script provide" type */
  616.     wa = may_be_linker_script_provide_symbol(sa);
  617.     wb = may_be_linker_script_provide_symbol(sb);
  618.     if (wa != wb)
  619.         return wa - wb;
  620.  
  621.     /* sort by the number of prefix underscores */
  622.     wa = prefix_underscores_count((const char *)sa->sym + 1);
  623.     wb = prefix_underscores_count((const char *)sb->sym + 1);
  624.     if (wa != wb)
  625.         return wa - wb;
  626.  
  627.     /* sort by initial order, so that other symbols are left undisturbed */
  628.     return sa->start_pos - sb->start_pos;
  629. }
  630.  
  631. static void sort_symbols(void)
  632. {
  633.     qsort(table, table_cnt, sizeof(struct sym_entry), compare_symbols);
  634. }
  635.  
  636. int main(int argc, char **argv)
  637. {
  638.     if (argc >= 2) {
  639.         int i;
  640.         for (i = 1; i < argc; i++) {
  641.             if(strcmp(argv[i], "--all-symbols") == 0)
  642.                 all_symbols = 1;
  643.             else if (strncmp(argv[i], "--symbol-prefix=", 16) == 0) {
  644.                 char *p = &argv[i][16];
  645.                 /* skip quote */
  646.                 if ((*p == '"' && *(p+2) == '"') || (*p == '\'' && *(p+2) == '\''))
  647.                     p++;
  648.                 symbol_prefix_char = *p;
  649.             } else
  650.                 usage();
  651.         }
  652.     } else if (argc != 1)
  653.         usage();
  654.  
  655.     read_map(stdin);
  656.     sort_symbols();
  657.     optimize_token_table();
  658.     write_src();
  659.  
  660.     return 0;
  661. }
  662.